动态规划（DP）通俗讲解 1、什么是动态规划？ 这里参考百度百科，动态规划是求解决策过程最优化的数学方法。把多阶段过程转化为一系列单阶段问题，利用各阶段之间的关系，逐个求解，创立了解决这类过程优化问题的新方法——动态规划。

2、什么时候要用动态规划？ 如果要求一个问题的最优解（通常是最大值或者最小值），而且该问题能够分解成若干个子问题，并且小问题之间也存在重叠的子问题，则考虑采用动态规划。

3、怎么使用动态规划？ 我把下面称为动态规划五部曲：

下面这个图是我们离散老师讲的一点动态规划，第一问是最基础的贪心，相信大家都会，第二问的DP如果是初学者建议把图片里的过程看一遍理解一下，（类似01背包）对理解下面的背包有好处。

考虑有 n 种物品，第 i 种物品的每个重量为 wi，价值为 vi，有无限多个。 我们手头有一个大小为 m的背包，需要算出能装下的最大总价值。

我们设 f(i) 表示大小为 i 的背包最多能装的价值，那么可以得到一个转移方程: f ( i ) = m a x f ( i − w   1   ) + v 1 , f ( i − w   2   ) + v 2 , . . . , f ( i − w   n   ) + v   n   f(i) = max{f(i − w~1~) + v1,f(i − w~2~) + v2,...,f(i − w~n~) + v~n~} f(i)=maxf(i−w 1 )+v1,f(i−w 2 )+v2,...,f(i−w n )+v n 写成简洁一些的形式: f ( i ) = m a x f ( i − w   j   ) + v   j   f(i) = max {f(i − w~j~) + v~j~} f(i)=maxf(i−w j )+v j 初始条件为: f ( 0 ) = 0 f(0) = 0 f(0)=0 尝试用代码来实现:

时间复杂度O(N−K)